package com.LeeCode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 销售价值减少的颜色球
 */

public class Code1648 {
    public static void main(String[] args) {
        int[] inventory = {1000000000};
        int orders = 1000000000;
        System.out.println(new Code1648().maxProfit(inventory, orders));
    }

    public int maxProfit(int[] inventory, int orders) {
        final int MOD = 1000000007;
        Arrays.sort(inventory);
        int n = inventory.length;
        long ans = 0;
        int cur = inventory[n - 1];
        int i = n - 1;

        while (orders > 0) {
            // 找到所有等于cur的库存
            while (i >= 0 && inventory[i] == cur) {
                i--;
            }
            // 下一个高度（可能是0）
            int next = i >= 0 ? inventory[i] : 0;
            // 可以连续取的次数
            int count = n - 1 - i;
            // 可以取的完整层数
            int rounds = Math.min(orders / count, cur - next);

            if (rounds > 0) {
                // 等差数列求和：(a1 + an) * n / 2
                long sum = (long) (cur + cur - rounds + 1) * rounds / 2 * count;
                ans = (ans + sum) % MOD;
                orders -= rounds * count;
                cur -= rounds;
            } else {
                // 处理剩余的orders
                ans = (ans + (long) cur * orders) % MOD;
                orders = 0;
            }
        }

        return (int) ans;
    }
}
